package com.mlh.backtracking;
import java.util.HashSet;
import java.util.Scanner;

/**
 * @author 缪林辉
 * @date 2024/10/12 17:24
 * @DESCRIPTION
 */
//给一个字符串n（长度不超过100），和数字m，取出所有可能的字符串组合，如输入abc和2，输出ab,ac,bc,ba,ca,cb
// 由于字符串n没有说每个字母只会出现一次，因此最终的结果需要用set来去重
public class KStringArrange {
    boolean[]flag;
    StringBuilder sb=new StringBuilder();
    HashSet<String>res=new HashSet<>();
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        String s = in.nextLine();
        int num=in.nextInt();
        KStringArrange ks = new KStringArrange();
        ks.method1(s,num);
    }

    public void method1(String s,int targetNum){
        flag=new boolean[s.length()];
        backTracking(s,targetNum,0);
        for (String temp :res) {
            System.out.print(temp+" ");
        }
    }

    private void backTracking(String s, int targetNum,int curNum) {
        if(curNum>=targetNum){
            String s1 = sb.toString();
            res.add(s1);
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            if(flag[i]){
                continue;
            }
            sb.append(s.charAt(i));
            flag[i]=true;
            backTracking(s,targetNum,curNum+1);
            flag[i]=false;
            sb.deleteCharAt(sb.length()-1);
        }
    }
}
